import typing
from provate import listNode, list2pList

# 题目：输入一个链表，输出该链表中倒数第k个节点，为了符合大多数人的习惯，本题从1开始计数，即链表中尾节点为倒数第1个节点

# 可以定义两个指针，使得第一个指针与第二个节点之间间隔k-1个节点，当第二个节点走到尾节点时候，那第一个节点就是倒数第k个节点

def kth2teil(head:listNode,k:int) -> (listNode or None):
    if not head or k<=0:
        return None

    p_1, p_2 = head, head
    for i in range(k-1):
        if p_1.next == None and i < k-1:
            return None
        p_1 = p_1.next
    while p_1.next is not None:
        p_1 = p_1.next
        p_2 = p_2.next
    return p_2



if __name__ == '__main__':
    l1 = [1,2,3,4,5,6,7,8]
    head = list2pList(l1)
    print(kth2teil(head, 5).value)
    print(kth2teil(head, 8).value)
    print(kth2teil(head, 9))
